package com.littrabble.graph;

public class Kruskal {

    public static final Integer NODE_NUM = 5;

    public static void main(String[] args) {

        int[] data = DisjointSet.makeset(NODE_NUM + 1);
        
        int[][] s = new int[NODE_NUM + 1][NODE_NUM + 1];
        s[1][2] = s[2][1] = 4;
        s[1][3] = s[3][1] = 2;
        s[1][4] = s[4][1] = 6;
        s[2][3] = s[3][2] = 1;
        s[2][4] = s[4][2] = 5;
        s[3][4] = s[4][3] = 7;
        s[3][5] = s[5][3] = 3;
        s[4][5] = s[5][4] = 9;
    }

}

class DisjointSet {

    public static int[] makeset(int n) {

        int[] data = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            data[i] = i;
        }

        return data;
    }

    public static int find(int node, int[] data) {

        int j = node;

        while (data[j] != j) {
            j = data[j];
        }

        return j;
    }

    public static void merge(int p, int q, int[] data) {
        if (p < q) {
            data[q] = p;
        } else {
            data[p] = q;
        }
    }
}